Internet Info 1994 March

home *** CD-ROM | disk | FTP | other *** search

/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / inet / internet-drafts / draft-ietf-pip-address-conv-00.txt < prev next >

Wrap

Text File | 1993-06-16 | 48KB | 1,216 lines

Pip Working Group P. Francis INTERNET-DRAFT (formerly P. Tsuchiya) Bellcore June 1993 Pip Address Conventions Status of this Memo This document is an Internet Draft. Internet Drafts are working documents of the Internet Engineering Task Force (IETF), its Areas, and its Working Groups. Note that other groups may also distribute working documents as Internet Drafts). Internet Drafts are draft documents valid for a maximum of six months. Internet Drafts may be Updated, replaced, or obsoleted by other documents at any time. It is not appropriate to use Internet Drafts as reference material or to cite them other than as a "working draft" or "work in progress." Please check the I-D abstract listing contained in each Internet Draft directory to learn the current status of this or any other Internet Draft. Abstract Pip is an internet protocol intended as the replacement for IP version 4. Pip is a general purpose internet protocol, designed to handle all forseeable internet protocol requirements. This specification is one of a number of documents that specify the operation of Pip. This specification describes the conventions for using the various Pip addresses--the hierarchical unicast address, the class-D style multicast address, the CBT multicast address, and the nearcast address. This specification does not describe how Pip addresses are assigned. Conventions All functions in this specification are mandatory. Pip WG, Expires December 1993 [Page 1] INTERNET-DRAFT Pip Addr Conventions June 1993 1. Introduction Addressing is the core of any internet architecture. Pip Addresses are carried in the Routing Directive (RD) of the Pip header (except for the Pip ID, which in certain circumstances functions as part of the Pip Address). Pip Addresses are used only for routing packets. They do not identify the source and destination of a Pip packet. The Pip ID does this. This memo describes the various Pip addressing types. There are four Pip Address types [2]. The hierarchical Pip Address (referred to simply as the Pip Address) is used for scalable unicast and for the unicast part of a CBT-style multicast and nearcast. The multicast part of a CBT-style multicast is the second Pip address type. The third Pip address type is class-D style multicast. The fourth type of Pip address is the so-called "nearcast" address. This address causes the packet to be forwarded to one of a class of desti- nations (such as, to the nearest DNS server). Bits 0 and 1 of the RC for the near-term Pip architecture indicate which of four address families the FTIFs and Dest ID apply to. The values are: Value Address Family ----- -------------- 00 Hierarchical Unicast Pip Address 01 Class D Style Multicast Address 10 CBT Style Multicast Address 11 Nearcast Pip Address The remaining bits are defined differently for different address fam- ilies, and are defined in the following sections. The RC Contents value associated with this RC definition is 1. 2. Hierarchical Unicast Pip Addresses 2.1. General Pip Addresses are hierarchical addresses. Pip Addresses are assigned such that a number at any level of the hierarchy is unique only with Pip WG, Expires December 1993 [Page 2] INTERNET-DRAFT Pip Addr Conventions June 1993 respect to the levels above it. Because of this, all Pip Address are unique. While the sole purpose of the Pip Address is to encode topologically significant addresses, the Pip Address does also represent a hierar- chy of Pip Address Assignment Authorities (PAAA). At the top of the PAAA hierarchy is the root PAAA. This PAAA assigns top-level Pip Address numbers. These numbers appear at the top of any fully- enumerated Pip Address. (By fully-enumerated, we mean a Pip Address where all levels of the address are given.) Pip Addresses signify either the location of a Pip system (host or router), or a subnetwork. In the latter case, the Pip ID is used to route a Pip packet to a Pip system across the subnetwork. Thus, a Pip Address or a Pip Address+ID causes a Pip packet to be routed to the Pip processing module of a given Pip system, after which the Pro- tocol field of the Pip header is used for further demultiplexing. (This having been said, the extension of a Pip Address on the least significant end to signify sub-system entities, such as processors within a multi-process host, or peripherals such as a screen or disk, is possible. Such use is a local matter--it does not effect Pip routing outside the host. Such use is outside the scope of this specification.) 2.2. Routing Context (RC) Structure When the RC Contents field is 1, bits 0 and 1 of the Routing Context (RC) indicate the address family. If the address family is Pip Hierarchical Unicast Address, then bits 0 and 1 are value 00. When this RC indicates Pip Hierarchical Unicast Address (called simply the Pip Address in this document), the RC is structured as follows: bits meaning ---- ------- 0,1 address family (= 00) 2,3 level 4,5 metalevel 6 exit routing type This document discusses the conventions for handling Pip Addresses and their related Routing Context. Pip WG, Expires December 1993 [Page 3] INTERNET-DRAFT Pip Addr Conventions June 1993 2.3. Pip Addresses in the Pip Header The Pip header carries Pip Addresses as a sequence of FTIFs (Forward- ing Table Index Fields). Each FTIF is 16 bits in length. Usually, each FTIF represents one layer of the hierarchy, although it is pos- sible for a single hierarchy layer to span multiple 16-bit FTIFs. The sequence of FTIFs is called the FTIF Chain. Both the source and destination Pip Addresses are carried in the same FTIF Chain. The source Pip Address comes first, and is written in order of lowest hierarchy level first. The destination Pip Address follows, and is written in order of highest hierarchy level first. Note that, depending on the locations of source and destination rela- tive to each other, it is not always necessary to include the top levels of the Pip Address in the FTIF Chain. The least significant bits of each FTIF is the relator. The three relator types are: value type ----- ---- last bit = 0 horizontal last 5 bits = 11111 extension all others vertical The relator indicates what the relationship between the current and subsequent FTIF is. Horizontal indicates that the subsequent FTIF is a separate Pip Address number, but that the number is neither hierarchically above nor below the current one. Vertical indicates that the subsequent FTIF is a separate Pip Address number, and that number is hierarchically above or below the current one. Extension indicates that the subsequent FTIF is part of the same Pip Address number. When a Pip Address number is greater than 15 bits in length, then the extension must be used to encode the number. When an extension is used, the Pip Address number is right-justified. For instance, if the Pip address number (without the relator) is hex 89ab, and the subsequent number is below it, then it is written as 3f,1357 The last bit of "1357" is neither "0" nor "11111", which means vertical. The last five bits of "3f" are "11111", which means extension. The extension is needed because the vertical relator caused the number to be 17 bits long, thus forcing the extension. The reason for using five bits to encode extension and one bit to Pip WG, Expires December 1993 [Page 4] INTERNET-DRAFT Pip Addr Conventions June 1993 encode horizontal and vertical is to 1) maximize the code space available for horizontal and vertical use (each type gets roughly 1/2 the code space), and 2) maximize the use of forwarding table memory for the common case of direct index into the forwarding table. If we used 2 bits to encode all three relators, then vertical and horizon- tal would each get only 1/4 of the available code space. The reason we five bits rather than, say, 4 or 6, is that a 5 bit relator allows 48 bit numbers to be encoded in 4 16-bit FTIFs (rather than 5 FTIFs as would be the case with a 6 bit relator), while still allowing 64 bit numbers to be encoded in 6 FTIFs (as would also be the case with a 4 bit relator). Any Pip Address number is limited in size to 64 bits. This allows a Pip ID to be used as a Pip Address number if desired. When a single 64-bit Pip Address number is notated, it consists of 6 FTIFs. The first five have 5-bit extension relators. The sixth has the "true" relator, which may be vertical or horizontal, depending on the con- text of the number. 2.4. Assignment of Pip Addresses The root PAAA assigns top-level Pip Address numbers to two types of entities--providers and private networks. (Note that in this paper, a "private network" is often referred to as a "subscriber network" to indicate its role as a subscriber of network services from a pro- vider.) Pip Addresses with a provider at the top-level are called provider-rooted Pip Addresses. Pip Addresses with a private network at the top-level are called private-rooted Pip Addresses. The purpose of assigning numbers to providers is to allow good scal- ing characteristics at the top level of routing (because only routes to top level providers need be calculated), and to allow for policy routing, particularly provider selection. The purpose of assigning numbers to private networks is to give the systems in the private network globally unique Pip Addresses that are not dependent on the private network's service provider. The top- level private network numbers are not advertised outside of the private network, and except for intra-private network communications, and even then only rarely, never appear in Pip headers. Top-level private network numbers are primarily used to allow hosts to deter- mine when another host is in the same private network [9]. Pip WG, Expires December 1993 [Page 5] INTERNET-DRAFT Pip Addr Conventions June 1993 A Pip Address consists of zero or more Pip Address numbers with hor- izontal relators, followed by one or more Pip Address numbers with vertical relators, and ending with zero or one Pip Address numbers with a horizontal relator. The zero or more initial horizontal numbers represent a "route frag- ment". Horizontal numbers are used when 1) the "top" of a Pip Address (the first vertical number, representing a provider) is not advertised globally, and so another provider that is must be prepended to the Pip Address, or 2) the top of the Pip Address is advertised globally, but an adjacent provider represents a meaningful policy choice. (The top-level number of a private-rooted Pip Address always has a vertical relator.) For example, consider the following topology: other other big---BP1------BP2---big providers \ / providers \ / \ / LAP (local access provider) | | +---------------------+ | | | Sub1 | Area1----Area2 | (subscriber network) | | +---------------------+ Here we have a subscriber network (Sub1) connected to a local access provider (LAP), which is in turn connected to two Big Providers (BP1 and BP2). Because LAP is a provider, it has a top-level number. But, because LAP is only a local access provider, let's assume that it is not advertised outside of BP1 or BP2. Thus, the Pip Addresses of a subscriber host in Area1 are: BP1(hor),LAP(ver),Sub1(ver),Area1(hor) BP2(hor),LAP(ver),Sub1(ver),Area1(hor) Note that Pip Addresses are rooted at providers. Issues concerning provider-rooted addresses are discussed in [2] and [3]. These addresses would be advertised by DNS and carried in the FTIF Chain. Because BP1 or BP2 is advertised globally, packets from anywhere would reach BP1 or BP2. BP1 and BP2 know how to route to LAP, which Pip WG, Expires December 1993 [Page 6] INTERNET-DRAFT Pip Addr Conventions June 1993 knows how to route to Sub1, and so on. 2.5. Hierarchy Levels in Pip Addresses One reason that forwarding is fast with Pip is that the entire Pip Address does not have to be processed upon reception of a Pip packet. Rather, a router can just look at the relevant FTIF and forward the packet. To understand the appropriate context in which to interpret the FTIF, however, the Routing Context (RC) must be examined. The RC, among other things, contains information about the hierarchy level of the FTIF. This is necessary because it is possible for a given FTIF value to exist at any level of the hierarchy, and it is possible for a router to be operating at multiple levels of the hierarchy. Generally speaking, the level sub-field in the Routing Context (RC) is 0 for the highest level, and counts up one for each level deeper in the hierarchy. So, the top level of the hierarchy is level 0, the next level below that level 1, and so on. However, level alone is not enough to always determine the context of an FTIF. The following paragraphs explain why this is so. One of the goals of Pip is to isolate intra-domain (subscriber net- work) addressing from inter-domain (provider network) addressing con- ventions. The better we can isolate these two parts of the address, the better we can deal with address prefix changes, such as those that result from changing providers. (Note that, in the above exam- ple, BP1.LAP.Sub1 and BP2.LAP.Sub1 constitute the provider part of the addresses, and Area1 constitutes the subscriber part.) One of the techniques used to isolate subscriber and provider address parts is to allow the source and destination addresses of intra- domain packets (that is, packets between two hosts in the same sub- scriber network) to not encode the provider parts at all. In the context of the above example, this means that the FTIF Chain would not contain BP1.LAP.Sub1. Instead, it would contain only the Area1 part. By not requiring the provider part of the address to be in intra-domain packets, we allow network administrators to assign addresses internally without regard to the provider part. For instance, in the subscriber network the administrator should be able to assign numbers to Area1 and Area2 without concern for what pro- vider prefixes it has or may have in the future. Pip WG, Expires December 1993 [Page 7] INTERNET-DRAFT Pip Addr Conventions June 1993 In order to do this, the administrator must not only be isolated from the value of the provider prefix, but also from the number of levels in the provider prefix. But, the level is needed by subscriber routers to know how to forward based on examination of a single FTIF. Therefore, level alone is not enough to determine the context of an FTIF. To see why this is so, consider the following example: ----BP1--------BP2---- | | | | +---------------------+ | | | | Sub1 | Area1--R1--Area2 | (subscriber network) | | | | | subArea2 | | | +---------------------+ Here we have a subscriber network (Sub1) attached to two providers (BP1 and BP2) at two internal areas (Area1 and Area2 respectively). Area2 has a another layer of hierarchy below it (subArea2). Attached to Area1, Area2, and subArea2 is a router R1. Assume that the prefix given to Sub1 from BP1 is 1-2-3, and the prefix given to Sub2 from BP2 is 2-3. In other words, the top-level number of BP1 is 1 and the top-level number given to BP2 is 2. Both BP1 and BP2 have assigned the number 3 to Sub1. However, BP1 has an internal level of hierar- chy whereas BP2 does not. Thus, BP1's prefix has three numbers while BP2's prefix has only two. Assume further that Area1 is assigned the number 2, Area2 is assigned the number 3, and subArea2 is assigned the number 2. Thus, the Pip Addresses for hosts in Area1 are: 1-2-3-2 2-3-2 and the Pip Addresses for hosts in subArea2 are: 1-2-3-3-2 2-3-3-2 (Note that these Pip Addresses are not notated properly. For the sake of simplicity, the relator bits are not shown in this example.) Now, assume that we try to use level alone to indicate the appropri- ate hierarchy level in the RC field. Assume that router R1 receives a packet with level=3 and FTIF=2 (where level=0 is the top level). Router R1 cannot determine if this packet is for something in Area1 Pip WG, Expires December 1993 [Page 8] INTERNET-DRAFT Pip Addr Conventions June 1993 (1-2-3-2), or subArea2 (2-3-3-2). Both can have FTIF=2 at level=3, depending on which provider address is used. Note that if the router parses the address from the top level down, it could resolve the ambiguity. However, this both results in a slower lookup, and weak- ens the isolation between provider and subscriber addressing (even internal packets would have to carry full addresses). To fix this ambiguity, and still allow for provider and subscriber address isolation, we introduce a second subfield into the RC, the metalevel field. Whereas there is a level boundary at every level of the hierarchy, there is a metalevel boundary only at those hierarchy boundaries where there is a reasonable probability that the hierarchy element will have multiple parents. This will normally be the case at significant administrative boundaries. (Note that horizontal administrative boundaries do not represent metalevel boundaries. Metalevel boundaries, like level boundaries, indicate different hierarchical levels.) The most significant metalevel boundary is that between provider and subscriber. Every provider/subscriber boundary must also be a metalevel boundary. There may be metalevel boundaries at lower lev- els in the hierarchy. There may not be metalevel boundaries above the provider/subscriber metalevel boundary. Metalevel numbering in the RC is similar to level numbering it that the highest metalevel is metalevel=0, the next lower metalevel boun- dary is metalevel=1, and so on. Level numbering starts over again at 0 at each metalevel boundary. Thus, the top-level of the hierarchy (the level at which the root PAAA assigns Pip numbers) is metalevel=0, level=0. The next level down (if it is not at the provider/subscriber boundary) is metalevel=0, level=1. This level could, for instance, be a hierarchy level within the provider to allow for better scaling in the provider network. This numbering continues for all additional levels above the provider/subscriber boundary (that is, metalevel=0, level=2; metalevel=0, level=3, and so on). At the provider/subscriber boundary, the metalevel is incremented and the level reset to 0. Thus, the level just below the provider/subscriber boundary is metalevel=1, level=0. The next level down is metalevel=1, level=1, and so on. Thus, a packet between two hosts in the same subscriber network is transmitted at metalevel=1, level=0, regardless of the provider prefixes owned by those two hosts. This allows "hard-coded" configuration of Pip Addresses for intra-subscriber destinations. (By hard-coded, I mean static Pip WG, Expires December 1993 [Page 9] INTERNET-DRAFT Pip Addr Conventions June 1993 configuration of a Pip Address in a computer such that the Pip Address is not subject to auto-configuration protocols. An example of this is to put a Pip Address in an ASCII configuration file used by an application.) It also allows a private network to operate without connecting to any providers at all. When such a private net- work connects to a provider, it can then obtain one or more provider prefixes. Note that it is not a good idea to "hard-code" Pip Addresses with the private-rooted address prefix, because even these prefixes are sub- ject to change, for instance when two private networks merge. 2.6. Pip Address Notation This section describes how to notate a Pip Address (for instance, in an ASCII file). There is only one way to notate a Pip Address. Pip Address notation closely resembles the encoding of a Pip Address in a Pip header. The Pip Address is notated as a series of hex numbers separated by commas (",") and dots ("."). Each hex number can be between one and four digits in length. Up to four digits are needed to encode a 16- bit FTIF. The relators, including the extension relator, are included in the hex number. When notating a Pip Address, a comma is used at address positions where a metalevel boundary exists. A dot is used otherwise. When notating a Pip Address, the left-most (high-order, or higher- in-the-hierarchy) hex number must be at a metalevel boundary, and must be a level=0 Pip Address number. Leading commas are used to indicate the metalevel boundary of the Pip Address. A Pip Address notated from the root of the Pip Address hierarchy (metalevel=0) has no leading commas. A Pip Address notated from the top of the private network portion of the Pip Address hierarchy (metalevel=1) has a sin- gle leading comma. A Pip Address rooted at metalevel=2 has two lead- ing commas, and a Pip Address rooted at metalevel=3 has three leading commas. The maximum number of metalevels is four (encoded as two bits in the RC). The following network is used to illustrate Pip Address notation. BP1 and BP2 are big providers that are advertised globally by the routing protocol. LAP is a local access provider that is not Pip WG, Expires December 1993 [Page 10] INTERNET-DRAFT Pip Addr Conventions June 1993 advertised globally. Sub1 is the subscriber network. Area1 and Area2 are areas inside the subscriber network. subArea2 is an area within Area2. There is a single metalevel boundary--between the sub- scriber network Sub1 and the providers, LAP and BP2. ---BP1----LAP--------BP2---- | | | | +---------------------+ | | | | Sub1 | Area1------Area2 | (subscriber network) | | | | subArea2 | | | +---------------------+ Assume the following Pip Address number assignments: network assignment component # ( << 1) notes --------- ---------- ----- BP1 23 (46) top-level number BP2 9a (134) top-level number LAP 1b9 (372) top-level number Sub1 493aa (92754) top-level number LAP/Sub1 43 (86) assigned to Sub1 by LAP PAAA BP2/Sub1 11a (234) assigned to Sub1 by BP2 PAAA Area1 b3 (166) assigned by Sub1 PAAA Area2 71 (e2) assigned by Sub1 PAAA Area2/subArea2 14 (28) assigned by Area2 PAAA Note that none of the numbers shown above include the relator. The number in parenthesis is the assigned number left shifted one. This is shown to more clearly indicate the number with the relator appended. A host in Area1 may have the following four Pip Addresses: Pip Address PAAA Hierarchy ----------- -------------- 1. 46.373.87,166 root.BP1.LAP.Sub1,Area1 2. 135.235,166 root.BP2.Sub1,Area1 3. 13f.2755,166 root.Sub1,Area1 4. ,166 private,Area1 Pip WG, Expires December 1993 [Page 11] INTERNET-DRAFT Pip Addr Conventions June 1993 The first two Pip Addresses are provider-rooted. These would be used by hosts in other private networks to reach the host in Area1. Note that the last bit of the first number of Pip Address 1 has a 0 as the least significant bit. This indicates a relator of horizontal. Since LAP has a top-level Pip Address number, it is not "under" BP1 in the address hierarchy. Never-the-less, BP1 is in the Pip Address as part of a route fragment either because LAP isn't advertised glo- bally by routing, or because being able to route paths through BP1 is important to hosts in Sub1. The third Pip Address is private-rooted. This address would not be used by hosts outside of Sub1 to address hosts inside Area1, because Sub1 is not advertised globally. The third Pip Address would, how- ever, be advertised by DNS. This would allow other hosts in Sub1 to determine that the Area1 host was in the same private network (and thus, no provider prefix is needed to address the packet). The fourth Pip Address is not globally unique, and can only be used locally. The leading comma indicates that the top level of this address is at metalevel=1. Thus, if a host creates a Pip header using the fourth Pip Address, it would know to set the metalevel sub- field in the RC field to 1. The fourth Pip Address would not be advertised in DNS. 2.7. Router Addressing Conventions A router plays several roles. First, it can of course receive Pip packets to be forwarded to another router or a host. Second, as the destination of Pip packets, it can itself be a host. Third, it can be the "target" of a Pip packet that must then be translated into an IP packet and forwarded. We use the term "target" rather than sink to indicate that, even though the FTIF Chain is structured to deliver the packet to the router, the router is not the ultimate destination of the packet. Fourth, the router can be the end of a tunnel, in which case it is the target of a Pip packet that is untunneled and forwarded. Thus, routers can be the targets of three kinds of packets-- those meant for it, those that need to be translated, and those that need to be untunneled. To distinguish between these three types, routers must have a different Pip Address for each type. In its role as a host, the router uses the Pip Address of the attached LAN if there is one, or simply the destination Pip Address assigned to the router if Pip WG, Expires December 1993 [Page 12] INTERNET-DRAFT Pip Addr Conventions June 1993 there isn't. If the router is a target system either as a tunnel endpoint or for translation, then it must have distinct Pip Addresses for each of these cases. These Pip Addresses may or may not be interface specific, depending on the situation. Normally these Pip Addresses will all be identical except for the lowest FTIF. The exception to this rule is when the router is a border router. When a router is a Pip/IP translator, then it is a translator for a set of IP destinations. When a DNS lookup for one of these IP desti- nations is made, the Pip Address representing the router's role as a translator is returned (along with the router's Pip ID). In the case where the router is a tunnel endpoint, the Pip Address assigned for the purpose must be advertised to the router's peer tun- nel endpoints. When the router is the entry point of a tunnel, it puts this Pip Address in the source address location of the FTIF Chain of the Transit Part that it creates for the tunnel. When a Pip router inside a tunnel cannot deliver the packet to the tunnel exit router, it sends a PCMP error message back to either the source host or the tunnel entry router, depending on the cir- cumstances [5]. In the former case, the returned Pip packet is tar- geted to the original tunnel entry router, which becomes the tunnel exit router. In this case, the router untunnels the packet and for- wards it on. In the latter case, the tunnel entry router becomes the actual destination of the PCMP message. Because the tunnel endpoint router must be able to distinguish between being the tunnel exit system and being the recipient of the returned PCMP message, there must be a means by which the router that initiated the PCMP message can indicate the distinction. To do this, we use the following convention. When a tunnel endpoint is to untunnel a packet and forward it on, the relator of the last FTIF indicates horizontal. When a tunnel end- point is the recipient of a packet (that uses the router's tunnel Pip Address), the relator of the last FTIF indicates vertical. 2.8. Host Addressing Conventions Host Pip Addresses may be either LAN-based or host-based. In the Pip WG, Expires December 1993 [Page 13] INTERNET-DRAFT Pip Addr Conventions June 1993 former case, the host uses as its Pip Address the Pip Address of its attached LAN. (If there are multiple attached LANs, the host has multiple Pip Addresses.) The host's Pip ID is used to deliver the packet from a router (or another host) on the LAN to the host. That is, the Pip ID in the Dest ID field of the Pip header is examined to determine the appropriate LAN address to forward the packet to. If necessary, the Pip ID is also used to ARP for the destination host's LAN address. In the latter case (host-based), the FTIF Chain is sufficient to deliver the packet to the destination host. If the host is using host-based addressing, but is also attached to a LAN, then the host could have a Pip Address prefix that matches the LAN Pip Address. This address prefix would be followed by one or more FTIFs. In order for a router to distinguish between LAN-based and host-based Pip Addresses for hosts on its attached LAN, we use the following convention. If the host is using LAN-based addressing, then the FTIF representing the LAN (in this case, the last FTIF) has a horizontal relator. If the host is using host-based addressing, then the FTIF representing the LAN (in this case, not the last FTIF) has a vertical relator. 2.9. Reversing an FTIF Chain with Pip Addresses There are two cases where a Pip system may want to "reverse" an FTIF Chain with Pip Address. Reversing an FTIF Chain is the process of creating a new FTIF Chain that allows the packet to get back to the source host. The first case is that of a destination host returning a packet to the source host. The second case is that of a router returning a PCMP message back to the source host or a tunnel entry system. In the following descriptions, we assume that an FTIF Chain of the following form is received: Pip WG, Expires December 1993 [Page 14] INTERNET-DRAFT Pip Addr Conventions June 1993 V1 V2...Vi H1...Hj Hj+1...Hj+k Hj+k+1...Hj+k+m V1 V2... Vn | | | | | | policy | | | source address | route | dest address | i >= 0, j >= 1, k >= 0, m >= 0, n >= 1 That is, the FTIF Chain starts with a source address that contains zero or more vertical FTIFs followed by at least one horizontal FTIF. This is followed by 0 or more horizontal FTIFs that make up the "pol- icy route". This is in turn followed by the destination address, made up of 0 or more horizontal FTIFs followed by one or more verti- cal FTIFs. (There is one exception to the dest address shown here, which is that in the case of returning a Pip packet to a tunnel entry point, the final FTIF may be horizontal.) 2.9.1. Host FTIF Chain Reversal To reverse an FTIF Chain, the host first extracts the destination Pip Address from the received FTIF Chain. The destination Pip Address can be determined by matching the trailing FTIFs against those of the host's own addresses. That is, FTIF Vn is compared against the host's lowest level address component, Vn-1 against the host's next lowest level address component, and so on. Note that the destination Pip Address may be a partial address, com- ing under a metalevel boundary. In this case, there would be no hor- izontal components in the destination address of the received FTIF Chain. The destination Pip Address of the received FTIF Chain must be one of the Pip Addresses of the host. This becomes the source Pip Address of the returned (reversed) Pip packet. The host then takes the remainder of the FTIF Chain and treats it as the destination Pip Address of the returned Pip packet. Note that the remainder of the FTIF Chain may in fact be more than the received source Pip Address, for instance because of the inclusion of a policy route in the FTIF Chain. From the perspective of the reversing host, however, this does not change things. At this point, the host has the source and "destination" Pip Addresses for the return Pip packet. The host sets the Active FTIF Pip WG, Expires December 1993 [Page 15] INTERNET-DRAFT Pip Addr Conventions June 1993 field, and the level, metalevel, and exit routing type subfields of the RC, according to the procedures described in [9]. 2.9.2. Router FTIF Chain Reversal To reverse an FTIF Chain, a router must first decide how much of the received source Pip Address is needed to return the packet. For instance, if the packet is destined to an inter-domain location, but has not yet left the private network, then only the private network part of the address (metalevel=1 cluster) is needed. There are three cases to handle; 1. The packet is in the source's metalevel>0 cluster, 2. The packet is at metalevel=0, 3. The packet is in the destination's metalevel>0 cluster The first case exists when the prefix of the source address in the received FTIF Chain matches one of those of the router's. Since the received FTIF Chain does not explicitly indicate which FTIFs consti- tute the source address, the router must compare prefixes by first finding the first horizontal FTIF of the FTIF Chain (H1). If this matches the lowest horizontal FTIF in one or more of the router's Pip Addresses (that is, the FTIF in the router's Pip Address correspond- ing to H1), then the router compares the FTIFs in its Pip Address corresponding to H2 through Hj against H2 through Hj in the received FTIF Chain, and the FTIFs in its Pip Address corresponding to Vi, Vi-1, and so on down to the metalevel boundary, against those in the received FTIF Chain. If all of these FTIFs match, then the router is in the same metalevel>0 cluster as the source, and does not need to include the common prefix in the return packet. That is, the series of FTIFs starting from the first FTIF and going up to the FTIF previous to the common prefix is considered to be the "source address" of the received FTIF Chain. If any of these FTIFs don't match, then the router considers the "potential source address" of the received FTIF Chain to be the series of FTIFs starting from the first FTIF and going up to the FTIF previous to the Active FTIF. If one of the horizontal FTIFs of the Pip WG, Expires December 1993 [Page 16] INTERNET-DRAFT Pip Addr Conventions June 1993 potential source address matches that of the router's provider net- work, then that FTIF and all subsequent FTIFs are stripped from the potential source address, and what remains is considered to be the "source address" of the received FTIF. (Note that this may not be the complete source address of the source host, but it is sufficient to route the packet back to the source host.) The series of FTIFs that are considered to be the source address of the received FTIF Chain are reversed and used as the destination address of the FTIF Chain of the return packet. The router then chooses one of its own Pip Addresses to be the source address in the return packet. Then the router creates an FTIF Chain, Active FTIF field, and level, metalevel, and exit routing type subfields of the RC according to the algorithm for host creation of a Pip header described above. 2.9.3. Reversal of Multiple FTIF Chains (Tunneling Case) If there are multiple FTIF Chains in the received Pip packet, then all of them must be reversed in the return Pip packet. Each indivi- dual FTIF Chain is reversed according to the rules stated above. The order of encapsulation in the returned packet is the same as the received packet. 3. CBT Style Multicast Addresses When bits 1 and 0 of the RC defined by RC Contents = 1 are set to 10, the FTIF and Dest ID indicate CBT (Core Based Tree) style multicast. The remainder of the bits are defined as follows: bits meaning ---- ------- 0,1 CBT Multicast (= 10) 2,3 level 4,5 metalevel 6 exit routing type 7 on-tree bit 8,9 scoping With CBT (Core-based Tree) multicast, there is a single multicast Pip WG, Expires December 1993 [Page 17] INTERNET-DRAFT Pip Addr Conventions June 1993 tree connecting the members (recipients) of the multicast group (as opposed to Class-D style multicast, where there is a tree per source). The tree emanates from a single "core" router. To transmit to the group, a packet is routed towards the core using unicast rout- ing. Once the packet reaches a router on the tree, it is multicast using a group ID. The FTIF Chain for CBT multicast contains the (unicast) Hierarchical Pip Address of the core router and the Pip Address of the source. The Dest ID field contains the group ID. A Pip CBT packet, then, has two phases of forwarding, a unicast phase and a multicast phase. The "on-tree" bit of the RC indicates which phase the packet is in. While in the unicast phase, the on-tree bit is set to 0, and the packet is forwarded as for Pip Addresses as described above. During this phase, the scoping bits are ignored. If during this phase the packet cannot be delivered, the PCMP Packet Not Delivered (PND) message is sent as though the original packet were a Pip Address. Once the packet reaches the multicast tree, it switches to multicast routing by changing the on-tree bit to 1 and using the Dest ID group address for forwarding. During this phase, bits 2-6 of the RC are ignored. PCMP messages are not sent in response to a packet in the on-tree phase of CBT multicast. The CBT specification [7] describes the forwarding of CBT packets for IP. For use with Pip, the CBT specification is used as is, with the following exceptions: 1. The source and destination Pip Addresses in the FTIF Chain take on the roles of the source and destination IP address, with the proviso that the packet is forwarded according to Pip Address forwarding rules. 2. The on-tree bit in the RC takes on the role of the on-tree bit in the CBT IP option. 3. The Dest ID of the Pip header takes on the role of the group ID in the CBT IP option. 4. The scoping bits in the RC take on the role of the scoping bits in the CBT IP option. Pip WG, Expires December 1993 [Page 18] INTERNET-DRAFT Pip Addr Conventions June 1993 4. Class D Style Multicast Addresses When bits 1 and 0 of the RC defined by RC Contents = 1 are set to 01, the FTIF and Dest ID indicate Class D style multicast. The remainder of the RC is defined as: bits meaning ---- ------- 0,1 Class D Style Multicast (= 01) 2,3 scoping By "class D" style multicast, we mean multicast using the algorithms developed for use with Class D addresses in IP (class D addresses are not used per se). This style of routing uses both source and desti- nation information to route the packet (source host address and des- tination multicast group). For Pip, the FTIF Chain holds the source Pip Address, in order of most significant hierarchy level first. The reason for putting the source Pip Address rather than the Source ID in the FTIF Chain is that use of the source Pip Address allows the multicast routing to take advantage of the hierarchical source address, as is being done with IP. The Dest ID field holds the multicast group. All of the existing IP Class D multicast addresses are used with Pip by virtue of the "local IP" Pip ID address space [8]. These addresses are necessary when a multicast group is partly Pip and partly IP. For a pure Pip multi- cast group, either an IP Class D multicast address can be used, or another (non-IP) Pip address. To forward a Class D multicast packet, a router first examines the FTIF Chain starting from the beginning (Active FTIF field = 1). FTIFs are examined in order until the source of the packet is unambi- guously determined. Note that the FTIF Chain only identifies the source subnet, not the source host. This is adequate to describe the multicast tree, since all trees coming from hosts on the same subnet will be identical. Bits 2 and 3 of the RC are the scoping bits. The use of these bits are for further study. As of this writing, there is no specification for a routing algorithm to create Class D style multicast trees with Pip. It is expected that such a specification will be written in the future. Pip WG, Expires December 1993 [Page 19] INTERNET-DRAFT Pip Addr Conventions June 1993 4.1. Nearcast Addressing Nearcast addressing is a new form of addressing that, for now, is peculiar to Pip. Nearcast addressing causes a packet to be routed to one (the "nearest") of a group of systems. Thus, nearcast is similar to multicast in that a nearcast address identifies a group of sys- tems. Nearcast is similar to unicast, however, in that it only delivers one packet. To do nearcast addressing, the (other unicast) routing algorithm must maintain a route to the nearest member of each nearcast group. Nearcast is particularly useful for discovery applications. It allows one of a class of systems to be found without prior knowledge of that system's unicast address. Pip uses nearcast to help auto- configure Pip hosts. When bits 1 and 0 of the RC defined by RC Contents = 1 are set to 11, the FTIF and Dest ID indicate Nearcast addressing. The remainder of the RC is defined as: bits meaning ---- ------- 0,1 Nearcast Address (= 11) 2,3 level 4,5 metalevel 6 exit routing type 7 nearcast active 8,9 scoping With nearcast routing, the packet is unicast, but to the nearest of a group of destinations. This type of routing is used by Pip for auto- configuration. Other applications, such as discovery protocols, may also use nearcast routing. Like CBT, Pip nearcast has two phases of operation, in this case the unicast phase and the nearcast phase. The unicast phase is for the purpose of getting the packet into a certain vicinity. The nearcast phase is to forward the packet to the nearest of a group of destina- tions in that vicinity. Thus, the RC has both unicast and nearcast information in it. During the unicast phase, the nearcast active bit is set to 0, and the packet is forwarded according to the rules of Pip Addressing. The scoping bits are ignored. Pip WG, Expires December 1993 [Page 20] INTERNET-DRAFT Pip Addr Conventions June 1993 The switch from the unicast phase to the nearcast phase is triggered by the presence of an FTIF of value 1 in the FTIF Chain. When this FTIF is reached, the nearcast active bit is set to 1, the scoping bits take effect, and bits 2 through 6 are ignored. When in the nearcast phase, forwarding is based on the Dest ID field. References [1] Francis, "Pip Header Processing", Internet-Draft [2] Francis, "Pip Near-term Architecture", Internet-Draft [3] Francis, "On the Assignment of Provider-rooted Addresses", Internet-Draft [4] Thomson, Francis, "Use of DNS with Pip", Internet-Draft [5] Francis, Govindan, "PCMP: Pip Control Message Protocol", Internet-Draft [6] Pip ARP (to be completed) [7] Ballardie, Francis, Crowcroft, "Core Based Trees (CBT), An Architecture for Scalable Inter-Domain Multicast Routing", Internet-draft. [8] Francis, "Pip Identifiers", Internet-Draft [9] Francis, "Pip Host Operation", Internet-Draft Pip WG, Expires December 1993 [Page 21]